// Copyright (c) 2005-2008, Simon Howard
// Permission to use, copy, modify, and/or distribute this software
// for any purpose with or without fee is hereby granted, provided
// that the above copyright notice and this permission notice appear
// in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
// WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
// AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
// CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
// NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

/// A dynamic array list that can grow as needed.
pub struct ArrayList<T> {
    data: Vec<T>,
}

impl<T> ArrayList<T> {
    /// Creates a new empty `ArrayList`.
    pub fn new() -> Self {
        ArrayList { data: Vec::new() }
    }

    /// Appends an element to the end of the list.
    pub fn append(&mut self, item: T) {
        self.data.push(item);
    }

    /// Prepends an element to the start of the list.
    pub fn prepend(&mut self, item: T) {
        self.data.insert(0, item);
    }

    /// Inserts an element at the specified index.
    pub fn insert(&mut self, index: usize, item: T) -> Result<(), &'static str> {
        if index > self.data.len() {
            return Err("Index out of bounds");
        }
        self.data.insert(index, item);
        Ok(())
    }

    /// Removes an element at the specified index.
    pub fn remove(&mut self, index: usize) -> Result<(), &'static str> {
        if index >= self.data.len() {
            return Err("Index out of bounds");
        }
        self.data.remove(index);
        Ok(())
    }

    /// Removes a range of elements from the list.
    pub fn remove_range(&mut self, start: usize, count: usize) -> Result<(), &'static str> {
        if start + count > self.data.len() {
            return Err("Range out of bounds");
        }
        self.data.drain(start..start + count);
        Ok(())
    }

    /// Clears the list, removing all elements.
    pub fn clear(&mut self) {
        self.data.clear();
    }

    /// Returns the index of the first occurrence of the specified value.
    pub fn index_of<F>(&self, predicate: F) -> Option<usize>
    where
        F: Fn(&T) -> bool,
    {
        self.data.iter().position(predicate)
    }

    /// Sorts the list using the provided comparison function.
    pub fn sort<F>(&mut self, compare: F)
    where
        F: Fn(&T, &T) -> std::cmp::Ordering,
    {
        self.data.sort_by(compare);
    }

    /// Returns the length of the list.
    pub fn len(&self) -> usize {
        self.data.len()
    }

    /// Returns true if the list is empty.
    pub fn is_empty(&self) -> bool {
        self.data.is_empty()
    }

    /// Returns a reference to the element at the specified index.
    pub fn get(&self, index: usize) -> Option<&T> {
        self.data.get(index)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_arraylist_new_free() {
        let mut list: ArrayList<i32> = ArrayList::new();
        assert!(list.is_empty());

        list.append(1);
        assert_eq!(list.len(), 1);
    }

    #[test]
    fn test_arraylist_append() {
        let mut list = ArrayList::new();
        assert_eq!(list.len(), 0);

        list.append(1);
        assert_eq!(list.len(), 1);
        assert_eq!(list.get(0), Some(&1));

        list.append(2);
        assert_eq!(list.len(), 2);
        assert_eq!(list.get(1), Some(&2));
    }

    #[test]
    fn test_arraylist_prepend() {
        let mut list = ArrayList::new();
        assert_eq!(list.len(), 0);

        list.prepend(1);
        assert_eq!(list.len(), 1);
        assert_eq!(list.get(0), Some(&1));

        list.prepend(2);
        assert_eq!(list.len(), 2);
        assert_eq!(list.get(0), Some(&2));
        assert_eq!(list.get(1), Some(&1));
    }

    #[test]
    fn test_arraylist_insert() {
        let mut list = ArrayList::new();
        list.append(1);
        list.append(2);
        list.append(3);

        list.insert(1, 4).unwrap();
        assert_eq!(list.len(), 4);
        assert_eq!(list.get(0), Some(&1));
        assert_eq!(list.get(1), Some(&4));
        assert_eq!(list.get(2), Some(&2));
        assert_eq!(list.get(3), Some(&3));
    }

    #[test]
    fn test_arraylist_remove() {
        let mut list = ArrayList::new();
        list.append(1);
        list.append(2);
        list.append(3);

        list.remove(1).unwrap();
        assert_eq!(list.len(), 2);
        assert_eq!(list.get(0), Some(&1));
        assert_eq!(list.get(1), Some(&3));
    }

    #[test]
    fn test_arraylist_remove_range() {
        let mut list = ArrayList::new();
        list.append(1);
        list.append(2);
        list.append(3);
        list.append(4);

        list.remove_range(1, 2).unwrap();
        assert_eq!(list.len(), 2);
        assert_eq!(list.get(0), Some(&1));
        assert_eq!(list.get(1), Some(&4));
    }

    #[test]
    fn test_arraylist_index_of() {
        let mut list = ArrayList::new();
        list.append(1);
        list.append(2);
        list.append(3);

        assert_eq!(list.index_of(|&x| x == 2), Some(1));
        assert_eq!(list.index_of(|&x| x == 4), None);
    }

    #[test]
    fn test_arraylist_clear() {
        let mut list = ArrayList::new();
        list.append(1);
        list.append(2);
        list.append(3);

        list.clear();
        assert_eq!(list.len(), 0);
    }

    #[test]
    fn test_arraylist_sort() {
        let mut list = ArrayList::new();
        list.append(3);
        list.append(1);
        list.append(2);

        list.sort(|a, b| a.cmp(b));
        assert_eq!(list.get(0), Some(&1));
        assert_eq!(list.get(1), Some(&2));
        assert_eq!(list.get(2), Some(&3));
    }
}
